/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/first-unique-number-in-data-stream-ii
   @Language: C++
   @Datetime: 19-03-17 12:52
   */

class DataStream {
	unordered_map<int,int> dict;    // num, index
	map<int,int> uniqnums;          // index, num
	int index;
public:

	DataStream(){
		// do intialization if necessary
		dict.clear();
		uniqnums.clear();
		index=0;
	}

	/**
	 * @param num: next number in stream
	 * @return: nothing
	 */
	void add(int num) {
		// write your code here
		unordered_map<int,int>::iterator it=dict.find(num);
		if (it==dict.end()){
			dict[num]=index;
			uniqnums[index++]=num;
		}
		else uniqnums.erase(it->second);
	}

	/**
	 * @return: the first unique number in stream
	 */
	int firstUnique() {
		// write your code here
		if (uniqnums.size()<1) return 0;
		else return uniqnums.begin()->second;
	}
};
